描述

日子棋，在棋盘上又有很多点不能走，请问走到终点的走法有几种。
赤裸裸的组合数，只是当时对Lucas定理不熟，也没记好板子，傻傻弄不清，龙哥还想用两个long long来容斥2^100次方，怎么写啊，我也是醉了。
好吧现在做出来了，用dp记忆，很方便。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <complex>
#include <cstdio>
using namespace std;
#define ll long long
#define mod 110119
ll n,m,r,ca,cnt,a,b,rig,up;
ll factorial[110200];    
ll mod_pow(ll a,ll n,ll p)  
{  
    ll ret=1,A=a;
    for(; n ; A=(A*A)%p,n>>=1) if(n & 1)ret=(ret*A)%p;  
    return ret;  
}  
  
void init_factorial(ll p)  
{  
    factorial[0] = 1;  
    for(ll i = 1;i <= p;i++)factorial[i] = factorial[i-1]*i%p;  
}  
  
ll C(ll a,ll k,ll p) //求C(n,m)%p p最大为10^5。a,b可以很大！  a个数中挑k个的组合数
{  
    ll re = 1;  
    for(; a && k ; a /= p , k /= p){
        ll aa = a%p;ll bb = k%p;  
        if(aa < bb) return 0; //这个是最后的改动！  
        re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;//这儿的求逆不可先处理  
    }
    return re;  
}  
ll Lucas(ll a,ll k ,ll p){
    if(a<0 || k<0 || a<k)return 0;
    else return C(a,k,p);
}
struct point
{
    ll x,y;
    bool operator < (const point & b)const{
        if(x==b.x)return y<b.y;
        return x<b.x;
    }
}rock[105];
inline ll cal_right(int x,int y){
    return (2*x-y)/3;
}
inline ll cal_up(int x,int y){
    return (2*y-x)/3;
}
ll dp[200];
int main(){
    init_factorial(mod);ca=0;
    //freopen("1002.in","r",stdin);
    //freopen("myout.out","w",stdout);
    while( ~scanf("%I64d%I64d%I64d",&n,&m,&r) ){
        n--,m--;
        cnt=0;bool steck=0;
        for(int i=1 ; i<=r ; i++){
            scanf("%I64d %I64d",&a,&b);
            a--,b--;
            if(a==n && b==m) steck=1;
            if((a+b)%3!=0 || 2*a<b || 2*b<a || a>=n || b>=m)continue;
            rock[++cnt].x=a;
            rock[cnt].y=b;
        }
        if((n+m)%3!=0 || 2*n<m || 2*m<n || steck)printf("Case #%I64d: 0\n",++ca);
        else{
            rock[++cnt].x = n;
            rock[cnt].y   = m;
            sort(rock+1,rock+1+cnt);
            for(int i=1 ; i<=cnt ;i++){
                ll step=(rock[i].x+rock[i].y)/3;
                ll right=rock[i].x-step,up=rock[i].y-step;
                dp[i]=Lucas(right+up,right,mod);
                for(int j=1; j<i ;j++){
                    ll dis= (rock[i].x - rock[j].x) + (rock[i].y - rock[j].y) ;
                    if(rock[j].x>=rock[i].x || rock[j].y>=rock[i].y || dis%3)continue;
                    ll sstep=dis/3;
                    ll rright=rock[i].x - rock[j].x - sstep,uup=rock[i].y - rock[j].y -sstep;
                    dp[i]=(dp[i] - (Lucas(rright+uup,rright,mod) * dp[j])%mod + mod)%mod;
                }
            }
            printf("Case #%I64d: %I64d\n",++ca,dp[cnt]);
        }
    }
    return 0;
}